package weekMatch.one_341;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeeCode_04 {
    private List<Integer>[] g;
    private int[] price, cnt;
    private int end;
    public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
        g = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            g[edge[0]].add(edge[1]);
            g[edge[1]].add(edge[0]);
        }
        this.price = price;
        cnt = new int[n];
        for (int[] trip : trips) {
            end = trip[1];
            path(trip[0], -1);
        }
        int[] p = dfs(0, -1);
        return Math.min(p[0], p[1]);
    }
    private int[] dfs(int x, int fa){
        int notHalf = cnt[x] * price[x];
        int half = notHalf / 2;
        for (Integer y : g[x]) {
            if (y != fa) {
                int[] p = dfs(y, x);
                notHalf += Math.min(p[0], p[1]);
                half += p[0];
            }
        }
        return new int[]{notHalf, half};
    }
    private boolean path(int x, int fa){
        if (x == end){
            ++cnt[x];
            return true;
        }
        for (Integer y : g[x]) {
            if (y != fa && path(y, x)){
                ++cnt[x];
                return true;
            }
        }
        return false;
    }
}
